package com.leetcode.sort.basic_sort;

/**
 * @author Dennis Li
 * @date 2020/9/12 14:35
 */
public class ShellSort extends Sort {

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            int[] nums = generateArray();
            sort(nums);
            System.out.println(isSorted(nums));
        }
    }

    public static void sort(int[] nums) {
        int N = nums.length, h = 1;

        while (h < N / 3) {
            h = 1 + 3 * h;
        }

        // 拆分成h组的有序对。依次增加有序对长度，保证最终数列的有序
        while (h >= 1) {
            // 插入排序的一个重要特性就是左半部有序时排序很快，适合小数组
            for (int i = h; i < nums.length; i++) {
                for (int j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h /= 3;
        }

    }

    static class Practice extends Sort {

        public static void main(String[] args) {
            long start = System.currentTimeMillis();
            for (int i = 0; i < 10; i++) {
                int[] nums = generateArray(100000);
                sort(nums);
                System.out.println(isSorted(nums));
            }
            System.out.println(System.currentTimeMillis() - start);
        }

        public static void sort(int[] nums) {
            int h = nums.length / 2;

            while (h >= 1) {
                for (int i = h; i < nums.length; i++) {
                    for (int j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
                        swap(nums, j, j - h);
                    }
                }
                h /= 2;
            }

        }

    }

}
